package com.example.leetcode.leetcode;

import com.example.leetcode.leetcode.list.ListNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;



class SolutionTest {
    public static int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] == m) i = m + 1;
            else j = m - 1;
        }
        return i;
    }

    //二分法求缺失的第一个的一个整数
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        for (int i = 2000; i <= 3000; i++) {
            int result = binarySearch(nums, i);
            if (result == -1) {
                return i;
            }
        }
        return -1;
    }

    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int m = (left + right) / 2;
        while (left <= right) {
            if (nums[m] == target) {
                return m;
            } else if (nums[m] > target) {
                right = m - 1;
            } else {
                left = m + 1;
            }
        }
        return -1;
    }

    //搜索插入位置
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, m = (left + right) / 2;
        while (left <= right) {
            if (target == nums[m]) {
                return m;
            } else if (target > nums[m]) {
                left = m + 1;
                m = (left + right) / 2;
            } else {
                right = m - 1;
                m = (left + right) / 2;
            }
        }
        return left;
    }

    //910. 最小差值 II
    public int smallestRangeII(int[] A, int K) {
        int N = A.length;
        Arrays.sort(A);
        int ans = A[N - 1] - A[0];
        // 遍历
        for (int i = 0; i < A.length - 1; ++i) {
            int a = A[i], b = A[i + 1];
            int high = Math.max(A[N - 1] - K, a + K);
            int low = Math.min(A[0] + K, b - K);
            ans = Math.min(ans, high - low);
        }
        return ans;
    }

    public static int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        boolean flag = false;
        for (int i = 0; i < numbers.length; i++) {
            int left = 0, right = numbers.length - 1;
            int mid = (left + right) / 2 + left;
            if (flag) {
                return result;
            }
            while (left <= right) {
                if (numbers[mid] + numbers[i] == target) {
                    result[0] = i + 1;
                    result[1] = mid + 1;
                    flag = true;
                    break;
                }
                if (numbers[mid] + numbers[i] > target) {
                    right = mid - 1;
                    mid = (left + right) / 2;
                }
                if (numbers[mid] + numbers[i] < target) {
                    left = mid + 1;
                    mid = (left + right) / 2;
                }
            }
        }
        return result;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode hair=new ListNode(-1);
        hair.next=head;
        ListNode parent=hair;
        ListNode nodeSearch = head;
        ListNode p = head;
        int start = 0;
        while (p != null) {
            start++;
            if (start <= n) {
                p = p.next;
                if (p == null && start  == n) {
                    parent.next = nodeSearch.next;
                    nodeSearch.next = null;
                }
            } else  {
                parent = nodeSearch;
                nodeSearch = nodeSearch.next;
                start=start-2;
            }
        }
        return hair.next;
    }
    //347. 前 K 个高频元素
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> numsCount = new HashMap<>(16);
        for(int i=0;i<nums.length;i++){
            if(null!=numsCount.get(nums[i])){

            }
        }
        return null;
    }

    public static void main(String[] args) {

        int nums[] = {1, 2, 3, 4, 4, 9, 56, 90};
        ListNode l1=new ListNode(1);
        ListNode l2=new ListNode(2);
        ListNode l3=new ListNode(3);
        ListNode l4=new ListNode(4);
        ListNode l5=new ListNode(5);
//        l1.next=l2;
//        l2.next=l3;
//        l3.next=l4;
//        l4.next=l5;

        ListNode root=removeNthFromEnd(l1,1);
        while (root!=null){
            System.out.print(root.val);
            root=root.next;

        }
    }
}